#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Software: PyCharm
# @Version : Python-
# @Author  : Shengji He
# @Email   : hsjbit@163.com
# @File    : WordBreak2.py
# @Time    : 2020/11/1 14:15
# @Description:
from typing import List
from functools import lru_cache


class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        """
        Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s
        to construct a sentence where each word is a valid dictionary word. Return all such possible sentences.

        Note:
            - The same word in the dictionary may be reused multiple times in the segmentation.
            - You may assume the dictionary does not contain duplicate words.
        Example 1:
            Input:
                s = "catsanddog"
                wordDict = ["cat", "cats", "and", "sand", "dog"]
            Output:
                [
                  "cats and dog",
                  "cat sand dog"
                ]
        Example 2:
            Input:
                s = "pineapplepenapple"
                wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
            Output:
                [
                  "pine apple pen apple",
                  "pineapple pen apple",
                  "pine applepen apple"
                ]
            Explanation: Note that you are allowed to reuse a dictionary word.
        Example 3:
            Input:
                s = "catsandog"
                wordDict = ["cats", "dog", "sand", "and", "cat"]
            Output:
            []

        :param s:
        :param wordDict:
        :return:
        """

        @lru_cache(None)
        def backtrack(index: int) -> List[List[str]]:
            if index == len(s):
                return [[]]
            ans = []
            for i in range(index + 1, len(s) + 1):
                word = s[index: i]
                if word in wordSet:
                    nextWordBreaks = backtrack(i)
                    for nextWordBreak in nextWordBreaks:
                        ans.append(nextWordBreak.copy() + [word])
            return ans

        wordSet = set(wordDict)
        breakList = backtrack(0)
        return [' '.join(words[::-1]) for words in breakList]


if __name__ == '__main__':
    S = Solution()
    s = "catsanddog"
    wordDict = ["cat", "cats", "and", "sand", "dog"]
    print(S.wordBreak(s, wordDict))
    print('done')
